The invention relates generally to the field of digital signal processing. More specifically, embodiments of the invention relate to methods and systems for implementing finite impulse response filters without using multipliers.
Filtering is one of the most often used operations in digital signal processing. One method of filtering is by means of a finite impulse response (FIR) filter. In this type of filter, an input signal is convolved with an impulse response of finite duration that determines the frequency response output characteristics. Since an FIR is typically used in a sampled data system, the signal and the impulse response are quantized in time and amplitude yielding discrete samples. The discrete samples comprising the desired impulse response are the FIR filter coefficients.
The FIR filter calculation for each output sample is a two step process. A number of input signal samples are multiplied by a corresponding number of coefficient values (the values for each pair are multiplied together). Afterwards, all of the products are added together. The number and values of coefficients correspond with a desired frequency response. The longer the impulse response, the more filter coefficients and therefore the more multiplications are needed.
One disadvantage of FIR filters is the computational complexity required for each output sample. For example, for each output sample, N multiply-accumulate (MAC) operations need be performed. A 100 coefficient filter requires 100 multiplications and 100 additions for each output sample.
Digital signal processing (DSP) integrated circuits are specialized computational engines designed to simultaneously move sampled data from tap to tap while computing very large numbers of multiplications and additions. Despite many schemes for increased computational efficiency, a compromise between desired filter response and the number of taps is not uncommon. The tradeoff is between attenuation, flat response, ripple in the passband and attenuation region, transition bands and more. Other compromises have to do with computational accuracy. The number of bits available for both coefficients and input signal samples affect filter quality. The filter designer must take all of the above factors into consideration.
Despite the advances made in fabricating integrated circuits that reduce cost and the amount of chip area needed to implement multipliers, a multiplier remains relatively expensive when compared to other arithmetic operations such as adders. The expense is directly related to logic gate count. Binary adders are less costly than binary multipliers, however their use should be minimized as well. If the goal of a filter designer is to minimize cost and to conserve IC resources when implementing multichannel designs, it is desirable to find filtering architectures and methods which minimize, or obviate multipliers.
There are methods that reduce the number of multipliers used in filter implementations. For example, taking advantage of the symmetrical properties of filter coefficient impulse responses. However, the reduction is typically by a factor of 2 and in many applications is insufficient. Methods are also known that simplify the multipliers by choosing coefficients which are powers of 2, or sums of a small number of powers of 2. The simplification in this case is also insufficient since this type of filter usually requires a second filter to improve the frequency response. Most methods that reduce the number of multipliers in their calculations perform poorly and their flexibility is limited.
There is a need for low-cost FIR filters with improved performance and flexibility for applications such as filtering input signals in the front-end of ultrasound systems, where cost and chip resources are a consideration.